All wireless communication standards involve the encoding and decoding of data. The purpose of encoding is to reduce the impact of noise on the transmitted data so that fewer errors appear in the received data. One typical part of the encoding process is interleaving of the data. Interleaving involves rearranging the sequence of data bits in a known pattern which has a low degree of correlation to the original, non-interleaved data. Both the interleaved and non-interleaved data are then further encoded and transmitted. Because of the low correlation between the interleaved and non-interleaved data, a disruption in one of the two messages will not similarly affect the other message.
One type of interleaver is known as the ARP interleaver. Interleavers of this type are specified for the Convolutional Turbo Coding (CTC) interleaver for the IEEE802.16 standard (“WiMax”) and for the TTAS.KO-06.0064 standard (“WiBro”). ARP interleavers are also under consideration for other standards under development. Each standard provides a specific ARP algorithm that produces an interleaved index based on the block size of the original message and a non-interleaved index. Through repetitive application of this algorithm, a complete table or sequence of interleaved indices may be generated for any block size supported by the standard. These indices are then used to rearrange, or interleave, the data message.
A primary problem in interleaver design is the generation of the interleaved indices for the many operating conditions that are allowed by the standards. Conventional ARP interleavers typically generate these indices using one of two approaches: a look-up table (LUT) approach or an interleaver machine approach.
Using the LUT approach, the ARP interleaver includes a complete, pre-calculated table (or tables) of interleaved indices that is stored in a memory. However, this approach consumes a large amount of memory as the memory is generally large enough to hold a complete table of indices for the largest expected data block size. In addition, a separate table of indices must be maintained in memory or calculated for each possible data block size. If tables for all block sizes are maintained in memory, then the size and cost of the memory increase substantially. However, if only one table is maintained in memory, then a new table must be calculated for each possible block size and loaded into memory, substantially degrading system performance.
The interleaver machine approach provides hardware or software to calculate indices as requested for a given block size and original index, thereby solving the memory problem of the LUT approach. However, this approach requires the use of multiplication, addition/subtraction, division, modulo and comparison operations, which are relatively large and expensive to implement in hardware and which require many calculation cycles when implemented in software. Therefore, there is a need in the art for a more efficient ARP interleaver.